#include<iostream>
#include<vector>
using namespace std;

namespace wei
{
	template<class T>
	class less
	{
	public:
		bool operator()(const T& left, const T& right)const
		{
			return left < right;
		}
	};
	template<class T>
	class Greater
	{
	public:
		bool operator()(const T& left, const T& right)const
		{
			return left > right;
		}
	};
	template <class T, class Contioner = std::vector<T>, class Compare = less<T>>
	class priority_queue
	{
	public:
		priority_queue()
		{}
 
		template<class Iterator>
		priority_queue(Iterator first, Iterator last)
			: _con(first, last) // 1、使用vector的区间构造函数来初始化_con
		{
			// 2、建堆：从完全二叉树的最后一个非叶子结点来进行向下调整
			for (int i = (size() - 2) / 2; i >= 0; i--)
			{
				AdjustDown(i);
			}
		}
 
		void push(T val)
		{
			// 1、将代插入的元素进行尾部插入
			_con.push_back(val);
 
			// 2、将该元素进行向上调整
			AdjustUp();
		}
 
		void pop()
		{
			if (empty())
				return;
			// 1、将堆顶元素与最后一个元素进行位置交换
			std::swap(_con[0], _con[size() - 1]);
 
			// 2、将换到最后一个位置的堆顶元素进行尾删
			_con.pop_back();
 
			// 3、将新的堆顶元素进行向下调整
			AdjustDown(0);
		}
 
		size_t size()
		{
			return _con.size();
		}
 
		const T& top()const
		{
			return _con[0];
		}
 
		bool empty()const
		{
			return _con.empty();
		}
	private:
		void AdjustDown(size_t parent)
		{
			size_t sz = size();
			size_t child = 2 * parent + 1;
			Compare com;
			while (child < sz)
			{
				// 如果左孩子存在  且  左孩子小于右孩子  就将child进行更新
				if (child + 1 < sz && com(_con[child], _con[child + 1]))
					child += 1;
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					parent = child;
					child = parent * 2 + 1;
				}
				else
					return;
			}
		}
		void AdjustUp()
		{
			size_t child = size() - 1;
			Compare com;
			size_t parent = (child - 1) / 2;
			while (child)
			{
				if (com(_con[parent], _con[child]))
				{
					std::swap(_con[parent], _con[child]);
					child = parent;
					parent = (child - 1) / 2;
				}
				else
					return;
			}
		}
	private:
		Contioner _con;
	};
}
 
void TestMyPriority_queue1()
{
	int array[] = { 1,3,9,5,2,8,6,7,4 };
	wei::priority_queue<int> q(array, array+sizeof(array)/sizeof(array[0]));
	cout << q.size() << endl;
	cout << q.top() << endl;
}
 
void TestMyPriority_queue2()
{
	wei::priority_queue<int> q;
	q.push(1);
	q.push(2);
	q.push(3);
	q.push(4);
	q.push(5);
	q.push(6);
	cout << q.size() << endl;
	cout << q.top() << endl;
	q.pop();
	q.pop();
	cout << q.size() << endl;
	cout << q.top() << endl;
}
 
void TestMyPriority_queue3()
{
	int array[] = { 1,3,9,5,2,8,6,7,4 };
	wei::priority_queue<int, vector<int>, wei::Greater<int>> q(array, array + sizeof(array) / sizeof(array[0]));
	cout << q.size() << endl;
	cout << q.top() << endl;
}

int main(){
    TestMyPriority_queue2();
    return 0;
}
